// 给定一个数字字符串s，该字符串已经按照下面的映射关系进行了编码
// A -> 1, B -> 2,...., Z ->26
// 基于上述映射的方法，现在对字符串s进行解码，即从数字到字母进行反向映射，如11106，可以映射为AAJK或者KJF
// 计算出共有多少种可能的解码方案

// 解题思路：动态规划
// 1. 划分阶段，按照字符串的结尾位置进行阶段划分
// 2. 定义状态，dp[i]表示为：字符串s前i个字符构成的字符串可能构成的翻译方案数
// 3. 状态转移方程，dp[i]的来源有两种情况
//      1. 使用了一个字符，对s[i]进行翻译，只要s[i] !=0，就可以被翻译为 A ~ I某个字母，此时方案数为dp[i]= dp[i-1]
//      2. 使用了两个字符，对s[i-1]s[i]进行翻译，只有s[i-1] != 0 ,且s[i-1]和s[i]组成的整数必须小于等于26才能翻译，可以翻译为J~Z中的某个字母，此时方案数为dp[i] = dp[i-2]
// 这两种情况有可能同时存在，也有可能同时不存在，在进行转移的时候，将符合要求的方案数叠加起来即可
// 状态转移方程可以写为：dp[i] += dp[i-1] + (dp[i-2](s[i-1]s[i] <= 26))
// 4. 初始条件
//      1. 字符串为空时，只有一个翻译方案，翻译为空字符串，即dp[0]=1
//      2. 字符串只有一个字符时，需要考虑该字符串是否为0， 不为0的话，dp[1] = 1,否则dp[1] = 0

// 时间复杂度： O(n)
// 空间复杂度： O(n)

function numDecodings(s) {
    let dp = new Array(s.length + 1).fill(0)
    dp[0] = 1
    for (let i = 1; i <= s.length; i++) {
        if (s[i-1] != '0') {
            dp[i] += dp[i-1]
        }        
        if (i >= 2 && s[i-2] != '0' && Number(s.slice(i - 2, i)) <= 26) {
            dp[i] += dp[i - 2]
        }
    }
    return dp[s.length]
}

let s = '11106'
console.log(numDecodings(s))